# -*- coding: utf-8 -*- 
# @project : 《剑指offer》
# @Author : created by bensonrachel on 2021/6/25
# @File : 树的子结构.py

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def hasSubtree(self, pRoot1, pRoot2):
        """
        :type pRoot1: TreeNode
        :type pRoot2: TreeNode
        :rtype: bool
        """
        if (pRoot1 == None or pRoot2 == None): return False
        # 以下都是非空情况，注意！
        if (self.isSame(pRoot1, pRoot2)): return True
        # 在当前节点实现了匹配
        return self.hasSubtree(pRoot1.left, pRoot2) or self.hasSubtree(pRoot1.right, pRoot2)
        # 遍历树A的左子树，右子树是否有与整个树B匹配

    def isSame(self, pRoot1, pRoot2):
        if (not pRoot2): return True  # 代表如果B对应的节点是NULL，则说明它的父节点已经和A的对应位置已经匹配了
        if (not pRoot1 or pRoot1.val != pRoot2.val): return False
        # 上面两个情况都不符合的话，就说明A树和B树的当前节点的值是一样的，才进入下面的递归。
        return self.isSame(pRoot1.left, pRoot2.left) and self.isSame(pRoot1.right, pRoot2.right)
        # 最后如果 B树的节点不为空， A树的节点也不为空， A树和B树的当前节点是匹配的。
        # 那么我们就递归到A和B的左子树，同时，A和B的右子树，看看是否匹配，注意这里是&&


